The present invention relates generally to the field of computer graphics, and particularly to generating models of graphics objects from range images.
Several techniques have been developed in research and industry for determining 3D geometry from a set of aligned range images, see Curlass xe2x80x9cFrom range scans to 3D models,xe2x80x9d Comp. Graphics, Vol. 33, No. 4, 1999.
Recent work has shown that volumetric methods are robust to scanner noise and alignment uncertainty and provide good quality, water-tight models, see Curlass et al. xe2x80x9cA volumetric method for building complex models from range images,xe2x80x9d Proc. SIGGRAPH""96, pp. 303-312, 1996, Hilton et al. xe2x80x9cReliable surface reconstruction from multiple range images,xe2x80x9d 4th Euro. Conf. Comp. Vis., pp. 117-126, 1996, and Wheeler xe2x80x9cAutomatic modeling and localization for object recognitionxe2x80x9d, Ph.D. Thesis, Carnegie Mellon University, 1996.
However, most of these methods suffer from limited resolution, large memory requirements and long processing time. In addition, these methods produce mesh models with an excessively large number of triangle.
These methods construct a range surface for each aligned range image, and fill a fixed resolution volumetric representation with signed distances from the range surfaces. The methods use various techniques to reduce the time required to fill and access the volumetric data, including run length encoding of the distance values, binary encoding of regions outside a bounded region of the surface, and a 3-color octree representation of the volume. The distance values from multiple scans can be combined probabilistically using order-independent, or incremental updating. These methods all build a triangle model of the iso-surface of the distance volume using a well known Marching Cubes technique, see Lorensen et al. in xe2x80x9cMarching Cubes: A High Resolution 3D Surface Construction Algorithm,xe2x80x9d Proc. SIGGRAPH ""87, pp. 163-169, 1987.
Constructing 3D range surfaces and computing distances from these iso-surfaces significantly increases computational requirements. If, instead, the distance field could be generated directly from 2D range images, model generation times could be greatly reduced.
However, range images do not provide true distance values. In the simplest case, a range image records the perpendicular projected distance from the object""s surface to the image plane. The projected distance field is the same as the true distance field in only two special cases: throughout the distance field for a planar surface exactly parallel to the image plane, and at the surface where both true distances and the projected distances are zero for any surface.
Other than the first case, the projected distance field differs from the true distance field for points off the surface. This results in artifacts when projected distance fields from different viewpoints are combined.
Prior art described in U.S. patent application Ser. No. 09/206,071xe2x80x9cA Method for Estimating Volumetric Distance Maps from 2D Depth Imagesxe2x80x9d filed by Frisken et al. on Dec. 4, 1999 showed that a 3D projected distance field can be corrected by dividing sampled distances by the magnitude of the local 3D gradient of the projected distance field. This results in a better approximation of the true distance field near the surface, yielding better results when combining projected distance fields. However, computing the 3D gradient of the projected distance field directly from sampled distance values can be prohibitively expensive since it can require six or more additional evaluations of the distance field per gradient.
Therefore, it is desired to determine corrective distance field gradients directly from range images rather than from 3D volumetric data.
The present invention provides a method for determining a 2D gradient magnitude image from a range image of an object from which the 3D gradient magnitude can be derived. The range image includes a plurality of intensity values at pixel locations. The intensity values correspond to distances to a surface of the object.
The method scales the range image so that a unit intensity value corresponds to a unit distance value. Then, for each pixel si,j in the range image, the method determines a horizontal central difference dx, and a vertical central difference dy. Then, the 2D gradient magnitude at each pixel si,j is set to one half of the square root of (dx2+dy2+4).
The magnitude of the gradient of a 3D projected distance field can then be determined at a 3D point p by perpendicularly projecting the point p onto a location (x, y) of the scaled range image, by interpolating the gradient magnitude at (x,y) from the corresponding 2D gradient magnitude image values near the location (x,y), and by setting the 3D gradient magnitude at p to the interpolated 2D gradient magnitude at (x,y).